#include <algorithm> // for std::max and std::min
#include <limits>    // for std::numeric_limits

// 二叉树节点定义
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 求二叉树的最大、最小深度
class Code04_DepthOfBinaryTree {
public:
    // 计算二叉树的最大深度
    static int maxDepth(TreeNode* root) {
        return root == nullptr ? 0 : std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

    // 计算二叉树的最小深度
    static int minDepth(TreeNode* root) {
        if (root == nullptr) {
            // 当前的树是空树
            return 0;
        }
        if (root->left == nullptr && root->right == nullptr) {
            // 当前root是叶节点
            return 1;
        }
        int ldeep = std::numeric_limits<int>::max();
        int rdeep = std::numeric_limits<int>::max();
        if (root->left != nullptr) {
            ldeep = minDepth(root->left);
        }
        if (root->right != nullptr) {
            rdeep = minDepth(root->right);
        }
        return std::min(ldeep, rdeep) + 1;
    }
};